\documentclass{ctexart}
\usepackage{listings}%插入代码
\usepackage{geometry}%设置页面大小边距等
\usepackage{graphicx}%插入图片
\usepackage{amssymb}%为了用\mathbb
\usepackage{amsmath}%数学方程的显示
\usepackage{listings}%插入代码
\usepackage{fancyhdr}%设置页眉页脚
\usepackage{lastpage}%总页数
\usepackage{hyperref}%引用网页
\usepackage{xcolor}
\usepackage{tikz}
\usepackage{float}
\usepackage{subcaption}


\geometry{a4paper,left=2cm,right=2cm,top=2cm,bottom=2cm}%一定要放在前面！
\pagestyle{fancy}%设置页眉页脚
\lhead{陈冠宇\ 3200102033}%页眉左
\chead{Numerical Methods for Differential Equations}%页眉中
\rhead{HW2}%章节信息
\cfoot{\thepage/\pageref{LastPage}}%当前页，记得调用前文提到的宏包
\lfoot{Zhejiang University}
\rfoot{School of Mathematical Sciences}
\renewcommand{\headrulewidth}{0.1mm}%页眉线宽，设为0可以去页眉线
\renewcommand{\footrulewidth}{0.1mm}%页脚线宽，设为0可以去页眉线
\setlength{\headwidth}{\textwidth}

\hypersetup{%设置网页链接颜色等
    colorlinks=true,%链接将会有颜色，默认是红色
    linkcolor=blue,%内部链接，那些由交叉引用生成的链接将会变为蓝色（blue）
    filecolor=magenta,%链接到本地文件的链接将会变为洋红色（magenta）
    urlcolor=blue,%链接到网站的链接将会变为蓝绿色（cyan）
    }

\newtheorem{theorem}{Theorem}
\newtheorem{proof}{Proof}
\newtheorem{solution}{Solution:}

\title{\textbf{微分方程数值解第一次作业}}
\date{\today}

\begin{document}
\subsection*{\uppercase\expandafter{\romannumeral 1}} Exercise 9.5
\begin{proof}
   Since we have $||r||_2 = ||Ae||_2\leq ||A||_2 ||e||_2$, then
   $$\begin{aligned}
    cond(A)||b||_2 &= ||A||\cdot ||A^{-1}||\cdot ||b||_2\\
    &\geq ||A||_2\cdot ||A^{-1}b||_2\\
    &= ||A||_2\cdot ||x||
   \end{aligned}$$

   $\Rightarrow \frac{1}{cond(A)}\cdot \frac{||r||_2}{||b||_2}\leq \frac{||A||_2\cdot ||e||_2}{||A||_2\cdot ||x||_2} = \frac{||e||_2}{||x||_2}$

   Similarly, we have
   $$\begin{aligned}
    cond(A)\cdot \frac{||r||_2}{||b||_2} &= ||A||_2\cdot ||A^{-1}||_2\cdot \frac{||r||_2}{||b||_2}\\
    &\geq \frac{||A||_2\cdot ||A^{-1}r||_2}{||Ax||_2}\\
    &\geq \frac{||A||_2\cdot ||e||_2}{||A||_2\cdot ||x||_2}\\
    &= \frac{||e||_2}{||x||_2}
   \end{aligned}$$

\end{proof}

\subsection*{\uppercase\expandafter{\romannumeral 2}} Exercise 9.8
\begin{solution}
    We have $cond(A) = ||A||_2\cdot ||A^{-1}||_2$ and $||A||_2 = \sqrt{\lambda_{max}(A^TA)}$.

    Since A is symmetric, then $A^TA = AA^T$.
    Assume $\omega$ is eigenvector of $A^TA$ with eigenvalue $\lambda$. Then we have $A^TA\omega = A^T\lambda \omega = A\lambda \omega = \lambda^2 \omega$.

    $\Rightarrow ||A||_2 = |\lambda_{max}(A)|$.

    Similarly, $$||A^{-1}||_2 = \sqrt{\lambda_{max}(A^{-T}A^{-1})} = \sqrt{\lambda_{max}(A^{-1}A^{-T})} = \sqrt{\lambda_{max}(A^{T}A)^{-1}} = \sqrt{\frac{1}{\lambda _{min}(A^TA)}} = \frac{1}{\lambda _{min}(A)}$$

    Then when $n=8$, we have $\lambda_k(A) = 4n^2sin^2(\frac{k\pi}{2n}) = 128sin^2(\frac{k\pi}{16}),k = 1\cdots 7$, then $cond(A) = \frac{sin^2(\frac{7\pi}{16})}{sin^2(\frac{\pi}{16})}$

    Similarly, $n = 1024$, $cond(A) = \frac{sin^2(\frac{1023\pi}{2048})}{sin^2(\frac{\pi}{2048})}$
\end{solution}

\subsection*{\uppercase\expandafter{\romannumeral 3}} Exercise  9.11
\begin{proof}
Since we have wavenumber $n = k$, then $n _{max} = n-1 = \frac{1}{h}$. If homogeneous Dirichlet conditions are imposed on the boundary points, the maximum number of alternation between local extrema is reduced by one. Hence we have$n _{max} = \frac{1}{h} - 1$.
\begin{figure}[H]
  \centering
  \includegraphics[width=0.8\textwidth]{Figure/9_11.png}
  \caption{9.11}
  \label{fig:example}
\end{figure}

\end{proof}


\subsection*{\uppercase\expandafter{\romannumeral 4}} Exercise 9.13
\begin{proof}
We can see that $sin(3\pi x) + sin(9\pi x) = 0$, when $x = \frac{j}{5}, j = 1\cdots 5$.
  \begin{figure}[H]
  \centering
  \includegraphics[width=0.8\textwidth]{Figure/9_14.png}
  \caption{9.14}
  \label{fig:example}
\end{figure}


\end{proof}


\subsection*{\uppercase\expandafter{\romannumeral 5}} Exercise 9.17
\begin{proof}
   $$\begin{aligned}
    x^{(k+1)} &= (1-\omega)x^{(k)}+\omega x^* = (1-\omega )x^{(k)} + \omega (T_Jx^{(k)}+c)\\
    &= \left((1-\omega)T + \omega D^{-1}(L+U)\right)x^{(k)}+ \omega c
   \end{aligned}$$

   That is $$\begin{aligned}
    T_\omega &= (1-\omega)T + \omega D^{-1}(L+U)\\
    &= I-\omega D^{-1}(D-L-U) = I- \omega D^{-1}A\\
    &= I - \frac{h^2\omega }{2}A
   \end{aligned}$$

   Naturally, we have $\lambda_k(T_\omega) = 1- \frac{h^2\omega }{2}\lambda_k(A_k) = 1-2\omega sin^2(\frac{k\pi}{2n})$.
\end{proof}

\subsection*{\uppercase\expandafter{\romannumeral 6}} Exercise 9.18
\begin{proof}
Since $\rho(T_\omega) = \max{\lambda_k(T_\omega)} = 1-2\omega sin^2(\frac{\pi}{2*64}) \geq 1-2sin^2(\frac{\pi}{2*64}) \approx 0.9988 $

Hence slow convergence.
   \begin{figure}[H]
  \centering
  \includegraphics[width=0.8\textwidth]{Figure/9_18.png}
  \caption{9.18}
  \label{fig:example}
\end{figure}
\end{proof}
\subsection*{\uppercase\expandafter{\romannumeral 7}} Exercise 9.21
\begin{proof}

Note iteration $l$,  then we have $(1-2\omega sin^2(\frac{k\pi}{2n}))^l = 0.01$, then we have $l(k)$:
\begin{figure}[H]
  \centering
  \begin{subfigure}[b]{0.4\textwidth}
    \includegraphics[width=\textwidth]{Figure/9_21(a).png}
    \caption{9.21(a)$\omega = 1$}
  \end{subfigure}
  \hfill
  \begin{subfigure}[b]{0.4\textwidth}
    \includegraphics[width=\textwidth]{Figure/9_21(b).png}
    \caption{9.21(b)$\omega = \frac{2}{3}$}
  \end{subfigure}
  \caption{9.21}
\end{figure}
As we can see when $\omega = 1$, i.e. regular Jacobi is only good for $16\leq k \leq 48$, while $\omega = \frac{2}{3}$, the modes $16 \leq k \leq 48$ are all damped out quickly.
\end{proof}
\subsection*{\uppercase\expandafter{\romannumeral 8}} Exercise 9.35
\begin{proof}
 The computational cost of an FMG cycle is
 $$2WU(1+2^{-D}+2^{-2D}+\cdots + 2^{-mD})(1+2^{-D}+2^{-2D}+\cdots + 2^{-mD})<\frac{2}{1-2^{-D}}\frac{1}{1-2^{-D}}WU = \frac{2}{(1-2^{-D})^2}WU$$

 Then when $D = 1,2,30$, the upper bounds are $8WU, \frac{32}{9}WU,\frac{128}{49}WU$, respectively.
\end{proof}

\subsection*{\uppercase\expandafter{\romannumeral 9}} Exercise 9.41
\begin{proof}
  Since we have $\lambda _ k = \left\{
  \begin{aligned}&1-2\omega sin^2(\frac{k\pi}{2n})\qquad 0< k <32\\
 & 1-2\omega sin^2(\frac{(n- k)\pi}{2n}) \qquad 32 < k <64 \end{aligned}\right.$, and $s_k, c_k < 1$, hence $c_i's$ magnitude are small;
 
 
 $\rho(TG) = \frac{c_1+c_4+\sqrt{(c_1-c_4)^2 + 4c_2c_3}}{2}$, we have the pic
 \begin{figure}[H]
  \centering
  \includegraphics[width=0.6\textwidth]{Figure/9_4164.png}
  \caption{9.11}
  \label{fig:example}
\end{figure}
 Then $\rho \approx 0.1.$
 
 When n = 64,$\omega = \frac{2}{3}$
 \begin{figure}[H]
  \centering
  \begin{subfigure}[b]{0.3\textwidth}
    \includegraphics[width=\textwidth]{Figure/9_41a.png}
    \caption{$\nu _1 = 0,\nu _2 = 0$}
  \end{subfigure}
  \hfill
  \begin{subfigure}[b]{0.3\textwidth}
    \includegraphics[width=\textwidth]{Figure/9_41b.png}
    \caption{$\nu _1 = 0,\nu _2 = 2$}
  \end{subfigure}
  \hfill
  \begin{subfigure}[b]{0.3\textwidth}
    \includegraphics[width=\textwidth]{Figure/9_41c.png}
    \caption{$\nu _1 = 1,\nu _2 = 1$}
  \end{subfigure}
\end{figure}

\begin{figure}[H]
  \centering
  \begin{subfigure}[b]{0.3\textwidth}
    \includegraphics[width=\textwidth]{Figure/9_41d.png}
    \caption{$\nu _1 = 2,\nu _2 = 0$}
  \end{subfigure}
  \hfill
  \begin{subfigure}[b]{0.3\textwidth}
    \includegraphics[width=\textwidth]{Figure/9_41e.png}
    \caption{$\nu _1 = 2,\nu _2 = 2$}
  \end{subfigure}
  \hfill
  \begin{subfigure}[b]{0.3\textwidth}
    \includegraphics[width=\textwidth]{Figure/9_41f.png}
    \caption{$\nu _1 = 4,\nu _2 = 0$}
  \end{subfigure}
\end{figure}

 When n = 128,$\omega = \frac{2}{3}$
 \begin{figure}[H]
  \centering
  \begin{subfigure}[b]{0.3\textwidth}
    \includegraphics[width=\textwidth]{Figure/9_41a1.png}
    \caption{$\nu _1 = 0,\nu _2 = 0$}
  \end{subfigure}
  \hfill
  \begin{subfigure}[b]{0.3\textwidth}
    \includegraphics[width=\textwidth]{Figure/9_41b1.png}
    \caption{$\nu _1 = 0,\nu _2 = 2$}
  \end{subfigure}
  \hfill
  \begin{subfigure}[b]{0.3\textwidth}
    \includegraphics[width=\textwidth]{Figure/9_41c1.png}
    \caption{$\nu _1 = 1,\nu _2 = 1$}
  \end{subfigure}
\end{figure}

\begin{figure}[H]
  \centering
  \begin{subfigure}[b]{0.3\textwidth}
    \includegraphics[width=\textwidth]{Figure/9_41d1.png}
    \caption{$\nu _1 = 2,\nu _2 = 0$}
  \end{subfigure}
  \hfill
  \begin{subfigure}[b]{0.3\textwidth}
    \includegraphics[width=\textwidth]{Figure/9_41e1.png}
    \caption{$\nu _1 = 2,\nu _2 = 2$}
  \end{subfigure}
  \hfill
  \begin{subfigure}[b]{0.3\textwidth}
    \includegraphics[width=\textwidth]{Figure/9_41f1.png}
    \caption{$\nu _1 = 4,\nu _2 = 0$}
  \end{subfigure}
\end{figure}
\end{proof}
\subsection*{\uppercase\expandafter{\romannumeral 10}} Exercise 9.45
\begin{proof}
    Since $\mathbb{R}^{n-1} = N(I_h^{2h})\bigoplus R(I_{2h}^h),  dim(R(I_h^{2h})) = dim(R(I_{2h}^{h})) = \frac{n}{2} - 1$ by lemma 9.43

    Then, we have $dim(R(I_h^{2h})) = \frac{n}{2} - 1, dim(R(I_h^{2h})) = n-1 - \frac{n}{2} - 1 = \frac{n}{2}$.
\end{proof}
\end{document} 